package list;

import java.util.HashSet;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class DoubleListNode {
	int val;
	DoubleListNode next;
	DoubleListNode prev;
	DoubleListNode() {
	}

	DoubleListNode(int val) {
		this.val = val;
	}

	DoubleListNode(int val, ListNode next) {
		this.val = val;
		this.next = next;
	}
}
class Solution1 {
	public static int MAX = 201;
	public static int[] set = new int[MAX];
	public static int m = 0;
    public ListNode deleteDuplicates(ListNode head) {
    	if(head == null || head.next==null) {
    		return head;
    	}
    	m++;
        set[100 + head.val] = m;
        ListNode prev = head, cur = head.next;
        while(cur!=null) {
        	if(set[cur.val+100]==m) {
        		prev.next = cur.next;//删除cur指向节点
        		cur = prev.next;//cur指向下一个节点。
        	}
        	else {
        		//set不包含节点cur.val
        		
        		//写入哈希表
        		set[cur.val+100]=m;
        		//调整
        		prev = cur;
        		cur = cur.next;
        	}
        }
        return head;//返回当前头节点
    }
}
public class Solution {
	public DoubleListNode reverseList(DoubleListNode head) {
		DoubleListNode pre = null,next=null;
		while(head != null) {
			next = head.next;
			
			//反转
			head.next = pre;
			head.prev = next;
			//----
			pre = head;
			head = next;
		}
		return pre;
    }
}


//Solution1改成Solution提交。
class Solution2 {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode node1 = head;
        int len = 0;
        ListNode leftPre = null, rightNext = null;
        while(node1 != null) {
        	len++;
        	leftPre = len == left - 1 ? node1 : leftPre;
        	rightNext = len == right + 1? node1 : rightNext;
        	node1 = node1.next;
        }
        
        if(left >= right || left < 1 || right > len) {
        	return head;
        }
        node1 = leftPre == null ? head : leftPre;
        //后面跟反转单链表的逻辑几乎相同
        ListNode node2 = node1.next;
        node1.next = rightNext;
        ListNode next = null;
        while (node2 != null) {
        	next = node2.next;
        	node2.next = node1;
        	node1 = node2;
        	node2 = next;
        }
        if(leftPre != null) {
        	leftPre.next = node1;
        	return head;
        }
        return node1;
    }
}
